package code1_100.code71_80;

/**
 * 给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
 *
 * 输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
 * 输出：[[1,0,1],[0,0,0],[1,0,1]]
 *
 * 输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
 * 输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]
 *
 * 注：请使用原地算法
 */
public class _73setZeros {

    /**
     * 思考：常规方法：首先遍历一遍矩阵，使用数组标记包含0的行和列，在进行遍历置零即可
     * 方法二：题解方法：用原数组第一行第一列作为标记数组，
     * 但第一行和第一列的数据会改变，使用单独的两个标记数组记录第一行和第一列的0元素，在进行置0即可。
     *
     * 执行用时：     * 1 ms     * , 在所有 Java 提交中击败了     * 97.59%     * 的用户
     * 内存消耗：     * 39.8 MB     * , 在所有 Java 提交中击败了     * 53.17%     * 的用户
     *
     * @param matrix
     */
    public void setZeroes(int[][] matrix) {
        int[] flagRow = new int[matrix.length];
        int[] flagCol = new int[matrix[0].length];
        // 标记数组已构建完成
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if(matrix[i][j]==0){
                    flagRow[i] = 1;
                    flagCol[j] = 1;
                }
            }
        }
        // 遍历进行置0
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (flagRow[i]==1){
                    matrix[i][j] = 0;
                }
                if(flagCol[j]==1){
                    matrix[i][j] = 0;
                }
            }
        }
    }

    /**
     * 第二种方法：使用数组第一行第一列作为标记数组，然后单独记录第一行和第一列的0情况
     *
     * 执行用时：     * 1 ms     * , 在所有 Java 提交中击败了     * 97.59%     * 的用户
     * 内存消耗：     * 39.7 MB     * , 在所有 Java 提交中击败了     * 99.64%     * 的用户
     * @param matrix
     */
    public void setZeroes2(int[][] matrix) {
        // row行，col列
        int rowOne = 0;
        int colOne = 0;
        // 第一行
        for (int i = 0; i < matrix[0].length; i++) {
            if(matrix[0][i]==0){
                rowOne = 1;
                break;
            }
        }
        // 第一列
        for (int i = 0; i < matrix.length; i++) {
            if(matrix[i][0]==0){
                colOne = 1;
                break;
            }
        }
        // 记录完第一行第一列后，用原数组第一行第一列进行记录
        for (int i = 1; i < matrix[0].length; i++) {
            for (int j = 1; j < matrix.length; j++) {
                if(matrix[j][i]==0){
                    matrix[0][i] = 0;
                    matrix[j][0] = 0;
                }
            }
        }
        // 使用目前已经记录的标志位进行置0；
        for (int i = 1; i < matrix[0].length; i++) {
            for (int j = 1; j < matrix.length; j++) {
                if(matrix[0][i]==0||matrix[j][0]==0){
                    matrix[j][i] = 0;
                }
            }
        }
        if(rowOne==1){
            for (int i = 0; i < matrix[0].length; i++) {
                matrix[0][i] = 0;
            }
        }
        if(colOne==1){
            for (int i = 0; i < matrix.length; i++) {
                matrix[i][0] = 0;
            }
        }
    }

}
